/*****************************************************************************
 * heap.c: Pairing-based implementation of client heap
 *****************************************************************************
 * Copyright (C) 2012
 *
 * Authors: Dan Larkin <danielhlarkin@gmail.com>
 *          Yonatan Naamad <cached@gmail.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *****************************************************************************/

#include "heap.h"
#include <stdint.h>
#include <stdlib.h>

static cpm_heap_node* cpm_heap_merge( cpm_heap *heap, cpm_heap_node *a, cpm_heap_node *b );
static cpm_heap_node* cpm_heap_collapse( cpm_heap *heap, cpm_heap_node *node );

cpm_heap* cpm_heap_init( int (*less)( void*, void* ) )
{
    cpm_heap *heap = calloc( 1, sizeof( cpm_heap ) );
    heap->less = less;

    return heap;
}

int cpm_heap_empty( cpm_heap *heap )
{
    return( heap->root == NULL );
}

/**
 * Takes an item-key pair to insert it into the heap and creates a new
 * corresponding node.  Merges the new node with the root of the heap.
 *
 * @param heap  Heap to insert into
 * @param item  Item to insert
 * @param key   Key to use for node priority
 * @return      Pointer to corresponding node
 */
cpm_heap_node* cpm_heap_insert( cpm_heap *heap, void *element )
{
    cpm_heap_node *wrapper = calloc( 1, sizeof( cpm_heap_node ) );
    wrapper->element = element;
    wrapper->prev = wrapper;
    wrapper->next = wrapper;
    
    heap->root = cpm_heap_merge( heap, heap->root, wrapper );

    return wrapper;
}

/**
 * Returns the item of minimum key.
 *
 * @param heap  Heap to query
 * @return      Minimum key item
 */
void* cpm_heap_find_min( cpm_heap *heap )
{
    if( heap->root == NULL )
        return NULL;
        
    return heap->root->element;
}

/**
 * Returns the item of minimum key after removing it from the heap.
 *
 * @param heap  Heap to query
 * @return      Minimum key item
 */
void* cpm_heap_delete_min( cpm_heap *heap )
{
    if( heap->root == NULL )
        return NULL;

    return( cpm_heap_delete( heap, heap->root ) );
}

/**
 * Deletes an arbitrary item from the heap and modifies heap structure
 * to preserve heap properties.  Requires that the location of the
 * item's corresponding node is known.  deletes the node from its list
 * of siblings, then merges all its children into a new tree and
 * subsequently merges that tree with the root.
 *
 * @param heap  Heap in which the node resides
 * @param node  Pointer to node corresponding to the item to delete
 * @return      Key of item deleted
 */
void* cpm_heap_delete( cpm_heap *heap, cpm_heap_node *node )
{
    void *element = node->element;

    if ( node == heap->root )
        heap->root = cpm_heap_collapse( heap, node->child );
    else
    {
        if ( node->prev->child == node )
            node->prev->child = node->next;
        else
            node->prev->next = node->next;

        if ( node->next != NULL )
            node->next->prev = node->prev;

        heap->root = cpm_heap_merge( heap, heap->root,
            cpm_heap_collapse( heap, node->child ) );
    }

    free( node );
    
    return element;
}

/**
 * If the item in the heap is modified in such a way to decrease the
 * key, then this function will update the heap to preserve heap
 * properties given a pointer to the corresponding node.  Cuts the node
 * from its list of siblings and merges it with the root.
 *
 * @param heap      Heap in which the node resides
 * @param node      Node to change
 */
void cpm_heap_decrease_key( cpm_heap *heap, cpm_heap_node *node )
{
    if ( node == heap->root || node == NULL )
        return;

    if ( node->prev->child == node )
        node->prev->child = node->next;
    else
        node->prev->next = node->next;

    if ( node->next != NULL )
        node->next->prev = node->prev;

    heap->root = cpm_heap_merge( heap, heap->root, node );
}

/**
 * If the item in the heap is modified in such a way to decrease the
 * key, then this function will update the heap to preserve heap
 * properties given a pointer to the corresponding node.  Cuts the node
 * from its list of siblings and merges it with the root.
 *
 * @param heap      Heap in which the node resides
 * @param node      Node to change
 */
cpm_heap_node* cpm_heap_increase_key( cpm_heap *heap, cpm_heap_node *node )
{
    void *element = node->element;
    cpm_heap_delete( heap, node );
    
    return cpm_heap_insert( heap, element );
}

/**
 * Merges two nodes together, making the item of greater key the child
 * of the other.
 *
 * @param heap  Heap in which to operate
 * @param a     First node
 * @param b     Second node
 * @return      Resulting tree root
 */
static cpm_heap_node* cpm_heap_merge( cpm_heap *heap, cpm_heap_node *a, cpm_heap_node *b )
{
    cpm_heap_node *parent, *child;

    if ( a == NULL )
        return b;
    else if ( b == NULL )
        return a;
    else if ( a == b )
        return a;

    if ( heap->less( b->element, a->element ) )
    {
        parent = b;
        child = a;
    }
    else
    {
        parent = a;
        child = b;
    }

    child->next = parent->child;
    if ( parent->child != NULL )
        parent->child->prev = child;
    child->prev = parent;
    parent->child = child;

    parent->next = NULL;
    parent->prev = NULL;

    return parent;
}

/**
 * Performs an iterative pairwise merging of a list of nodes until a
 * single tree remains.  Implements the two-pass method without using
 * explicit recursion (to prevent stack overflow with large lists).
 * Performs the first pass in place while maintaining a minimum of list
 * structure to iterate back through during the second pass.
 *
 * @param heap  Heap in which to operate
 * @param node  Head of the list to collapse
 * @return      Root of the collapsed tree
 */
static cpm_heap_node* cpm_heap_collapse( cpm_heap *heap, cpm_heap_node *node )
{
    cpm_heap_node *tail, *a, *b, *next, *result;

    if ( node == NULL )
        return NULL;

    next = node;
    tail = NULL;
    while ( next != NULL )
    {
        a = next;
        b = a->next;
        if ( b != NULL )
        {
            next = b->next;
            result = cpm_heap_merge( heap, a, b );
            // tack the result onto the end of the temporary list
            result->prev = tail;
            tail = result;                    
        }
        else
        {
            a->prev = tail;
            tail = a;
            break;
        }
    }
    
    result = NULL;
    while ( tail != NULL )
    {
        // trace back through to merge the list
        next = tail->prev;
        result = cpm_heap_merge( heap, result, tail );
        tail = next;
    }

    return result;
}
